package mao.leetcode.offer;

/**
 * @author Totoro
 * @date 2020/8/12
 * @explain:  >> 优先级低于 + 法。
 */
public class interview53 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {5, 7, 7, 8, 8, 10};
        int target = 8;
        solution.search(nums,target);
    }

    static class Solution {
        public int search(int[] nums, int target) {
            int index = binarySearch(nums,target);
            if (index < 0) return 0;
            int count=0,p=index;
            while(p>0 && nums[p--] == target) count++;
            p = index+1;
            while(p<nums.length && nums[p++] == target) count++;
            return count;
        }

        //二分查找模板，以后记住，就这么写。
        //若是查找不到需要返回插入位置，那么最后返回  lo,要是找不到报错，那么返回-1;
        public static int  binarySearch(int[] nums,int target){
            if(nums.length == 0) return 0;
            int lo =0,hi=nums.length-1,mid;
            while(lo <= hi){
                mid = lo+(hi-lo)/2;
                if(nums[mid] == target){
                    return mid;
                }else if(nums[mid] > target){
                    hi = mid-1;
                }else {
                    lo = mid+1;
                }
            }
            return -1;
        }
    }
}
